package com.onepiece.shipelves.common.myutils.tree;

public class BinaryTreeUtil {


    //查找二叉树的最长路径
    static int ans = 0;
    public static int diametorTree(TreeNode node){
        ans = 1;
        int depth = depth(node);
        System.out.println(depth);
        return ans - 1;

    }

    //每个节点的最大深度是看它的左树和右树的最大值+1，而最长路径是左树+右树深度+1
    //所以计算没有节点的最长路径，深度遍历之后就得到最大路径
    //每个节点只遍历了一次，所以时间复杂度为n，而空间复杂度因为只有递归的栈深度所以为O(height)
    private static int depth(TreeNode node) {
        if(node == null){
            return 0;
        }
        int L = depth(node.left);
        int R = depth(node.right);
        ans = Math.max(L + R + 1, ans);//这个计算最大长度的
        return Math.max(L, R) + 1;//这个是返回最大深度的
    }


    public static void main(String[] args) {
        TreeNode node1 = new TreeNode(3);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(3);
        node1.left = node2;
        node1.right = node3;
        int i = diametorTree(node1);
        System.out.println("path length" + ans);


    }

}
